package com.sicheng.lc.周赛.分类.dp.计数;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/26 11:12
 */
public class 统计放置房子的方式数 {
    //https://leetcode.cn/problems/count-number-of-ways-to-place-houses/
    public int countHousePlacements(int n) {
        long[] dp = new long[2];
        long mod = (long) 1e9 + 7;
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            long dp1 = dp[0] % mod;
            long dp0 = (dp[0] + dp[1]) % mod;
            dp[0] = dp0;
            dp[1] = dp1;
        }
        long l = (dp[0] + dp[1]) % mod;
        return (int) (l * l % mod);
    }

    public static void main(String[] args) {
        统计放置房子的方式数 s = new 统计放置房子的方式数();
        System.out.println(s.countHousePlacements(10000));
    }
}
